//搜索二维矩阵 II
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (matrix[mid][0] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        if (matrix[left][0] == target)
            return true;

         m = left;

        for (int i = 0; i <= m; i++) {
            left = 0;
            right = n - 1;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (matrix[i][mid] <= target)
                    left = mid;
                else
                    right = mid - 1;
            }
            if (matrix[i][left] == target)
                return true;
        }
        return false;
    }
};

//螺旋矩阵
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size();
        int n = matrix[0].size();
        int top = 0;
        int bottom = matrix.size() - 1;
        int left = 0;
        int right = matrix[0].size() - 1;

        while (left <= right && top <= bottom) {
            for (int i = left; i < right; i++) {
                ret.push_back(matrix[top][i]);
            }
            for (int j = top; j < bottom; j++) {
                ret.push_back(matrix[j][right]);
            }
            for (int i = right; i > left; i--) {
                ret.push_back(matrix[bottom][i]);
                if (top == bottom)
                    break;
            }
            for (int j = bottom; j > top; j--) {
                ret.push_back(matrix[j][left]);
                if (left == right)
                    break;
            }
            left++;
            top++;
            right--;
            bottom--;
        }
        if (m == n && m % 2)
            ret.push_back(matrix[m / 2][n / 2]);
        return ret;
    }
};